package solver

import (
	"math/rand"
	"slices"
	"time"
)

func (g *Grid) minCandidateCount() int {
	count := 9
	for _, row := range g.rows {
		for _, cell := range row.cells {
			if !cell.solved() && cell.candCount < count {
				count = cell.candCount
			}
		}
	}
	return count
}

func (g *Grid) selectMinUnsolved() []*Cell {
	minc := g.minCandidateCount()
	cells := []*Cell{}
	for _, row := range g.rows {
		for _, cell := range row.cells {
			if cell.solved() || cell.candCount > minc {
				continue
			}
			cells = append(cells, cell)
		}
	}
	return cells
}

func (g *Grid) choose() (cell *Cell) {
	cells := g.selectMinUnsolved()
	if len(cells) == 0 {
		return
	}
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	cell = cells[r.Intn(len(cells))]
	return
}

func filledCorrentlyHouse(house House) bool {
	values := []int{}
	for _, cell := range house.cells {
		if cell.solved() {
			values = append(values, cell.value)
		} else {
			if cell.candCount == 0 {
				return false
			}
		}
	}
	vmap := map[int]struct{}{}
	for _, v := range values {
		vmap[v] = struct{}{}
	}
	return len(vmap) == house.solvedCount
}

func (g *Grid) filledCorrenctly() (ok bool) {
	ok = true
	for _, row := range g.rows {
		if !filledCorrentlyHouse(row) {
			ok = false
			return
		}
	}
	for _, col := range g.cols {
		if !filledCorrentlyHouse(col) {
			ok = false
			return
		}
	}
	for _, box := range g.boxes {
		if !filledCorrentlyHouse(box) {
			ok = false
			return
		}
	}
	return
}

type State struct {
	g      Grid
	rowNum int
	colNum int
	cands  []int
}

func (g *Grid) guess(stack *[]State) (used bool) {
	cell := g.choose()
	if cell == nil {
		return
	}
	cands := intsFromBools(cell.cands)
	if len(cands) == 0 {
		return
	}
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	candIndex := r.Intn(len(cands))
	cand := cands[candIndex]
	cands = slices.Delete(cands, candIndex, candIndex+1)
	state := State{*g, cell.rowNum, cell.colNum, cands}
	*stack = append(*stack, state)
	g.solveOneCell(cell.rowNum, cell.colNum, cand+1)
	used = true
	return
}

func (g *Grid) back(stack *[]State) (used bool) {
	for {
		n := len(*stack)
		if n == 0 {
			return used
		}
		state := (*stack)[len(*stack)-1]
		//fmt.Println("n=", n, "keep=", keep.candIndex)
		cell := state.g.cells[state.rowNum][state.colNum]
		cands := state.cands
		//fmt.Println("n=", n, "cands=", cands, "keep=", keep.candIndex)

		if len(cands) == 0 {
			*stack = (*stack)[:len(*stack)-1]
			continue
		}
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		candIndex := r.Intn(len(cands))
		cand := cands[candIndex]
		cands = slices.Delete(cands, candIndex, candIndex+1)
		(*stack)[len(*stack)-1].cands = cands
		//fmt.Println(keep.candIndex, cands)
		*g = state.g

		g.Init()
		g.Clearup()
		g.solveOneCell(cell.rowNum, cell.colNum, cand+1)
		return true
		//fmt.Println(g.solvedCount, cell.rowNum, cell.colNum, cand+1)
	}

}

func (g *Grid) Backtrack() (used bool) {
	solvedCount := g.solvedCount

	var stack []State
	if !g.guess(&stack) {
		return false
	}
	for {
		g.Solve()
		if !g.filledCorrenctly() {
			if !g.back(&stack) {
				return false
			}
		} else if g.solvedCount == 81 {
			//fmt.Println("81!!", g.solvedCount)
			return solvedCount != g.solvedCount
		} else {
			used = g.guess(&stack)
			if !used {
				return false
			}
		}
	}
}
